package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class Subsets {

	List<List<Integer>> result = new ArrayList<List<Integer>>();
	List<Integer> list = new ArrayList<>();
	
	public static void main(String[] args) {
		Subsets object = new Subsets();
		int[] nums = {1, 2, 2};
		System.out.println(object.subsets2(nums));
	}
	
	public List<List<Integer>> subsets(int[] nums) {
		if(nums == null){
			return result;
		}
		result.add(list);	//首先加入空集
		backtrack(nums, 0);
		return result;
	}
	
	public void backtrack(int[] nums, int start){
//		if(start == nums.length){
//			result.add(new ArrayList<>(list));
//			return;
//		}
		for (int i = start; i < nums.length; i++) {
			list.add(nums[i]);
			result.add(new ArrayList<>(list));
			backtrack(nums, i + 1);
			list.remove(list.size() - 1);
		}
	}
	
	
	
	
	//如果包含重复元素
	Set<List<Integer>> result2 = new LinkedHashSet<List<Integer>>();
	List<Integer> list2 = new ArrayList<>();
	
	public List<List<Integer>> subsets2(int[] nums) {
		if(nums == null){
			return new ArrayList<List<Integer>>(result2);
		}
		result2.add(list2);	//首先加入空集
		Arrays.sort(nums);
		backtrack2(nums, 0, nums.length);
		return new ArrayList<List<Integer>>(result2);
	}
	
	public void backtrack2(int[] nums, int start, int end){
//		if(start == nums.length){
//			result.add(new ArrayList<>(list));
//			return;
//		}
		for (int i = start; i < nums.length; i++) {
			list2.add(nums[i]);
			result2.add(new ArrayList<>(list2));
			backtrack2(nums, i + 1, end);
			list2.remove(list2.size() - 1);
		}
	}
}
